#include <cstdio>

unsigned int mp[16][16] = {
	{1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1},
	{0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0},
	{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
	{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
	{0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
	{1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
	{1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
	{0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
	{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
	{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};

unsigned int dp[32][16];

int main(void)
{
	int re, n;

	for (int j = 0; j < 16; j++)
		dp[0][j] = 0;
	dp[0][0] = 1;
	for (int i = 1; i <= 30; i++) {
		for (int j = 0; j < 16; j++) {
			dp[i][j] = 0;
			for (int k = 0; k < 16; k++) {
				if(mp[k][j] != 0) {
					dp[i][j] += dp[i - 1][k];
				}
			}
		}
	}

	scanf("%d", &re);
	for (int ri = 1; ri <= re; ri++) {
		scanf("%d", &n);
		printf("%d %u\n", ri, dp[n][0]);
	}

	return 0;
}

//# 		Problem 	Verdict 	Language 	Run Time 	Submission Date
//805995 	3917 	Tiling a Grid With Dominoes 	Accepted 	C++ 	0.008 	2011-05-23 16:48:01
/*
id => 1174185
pid => 3917
pname => Tiling a Grid With Dominoes
status => Accepted
lang => C++
time => 0.009
date => 2012-12-14 17:35:26
*/
